'''
https://leetcode.cn/problems/diameter-of-n-ary-tree
'''
from typing import Optional, List


# Definition for a Node.
class Node:
    def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
        self.val = val
        self.children = children if children is not None else []

class Solution:
    def diameter(self, root: 'Node') -> int:
        """
        :type root: 'Node'
        :rtype: int
        """
        def f(root):
            if not root: return 0, 0
            max_child_line = 0
            second_max_child_line = 0
            ans = 0
            for child in root.children:
                child_line, child_ans = f(child)
                if child_line > max_child_line:
                    second_max_child_line = max_child_line
                    max_child_line = child_line
                elif child_line > second_max_child_line:
                    second_max_child_line = child_line
                ans = max(ans, child_ans)
            line = max_child_line + 1
            ans = max(ans, max_child_line + second_max_child_line + 1)
            return line, ans
        return f(root)[1] - 1